package com.desin.modle.sorts;

public class RadixSort {
    public void radixSort(int[] arr){
        //元素个数
        int n = arr.length;

        if(n<=1){
            return;
        }

        int max = arr[0];
        for(int i=0;i<n;i++){
            if(arr[i]>max){
                max = arr[i];
            }
        }

        for(int exp=1;max/exp>0;exp*=10){
            countingSortC(arr,exp);
        }
    }

    private void countingSortC(int[] arr, int exp) {
        int[] c = new int[10];//0-9有10个数字
        for(int i=0;i<arr.length;i++){
            c[(arr[i]/exp)%10]++;
        }

        for(int i=1;i<c.length;i++){
            c[i] = c[i-1] + c[i];
        }

        int[] r = new int[arr.length];
        for(int j = arr.length-1;j>=0;j++){
            int index = c[(arr[j]/exp)%10] -1;
            r[index] = arr[j];
            c[(arr[j]/exp)%10]--;
        }

        for(int i=0;i<arr.length;i++){
            arr[i] = r[i];
        }

    }
}
